//
// Created by yangchao on 2022/5/13.
// 29. 两数相除: https://leetcode.cn/problems/divide-two-integers/
//


#include <climits>
#include <iostream>
using namespace std;

/*****倍乘法****
 * https://leetcode.cn/problems/divide-two-integers/solution/tong-ge-lai-shua-ti-la-bei-zeng-cheng-fa-6qbg/
 * */
class Divide {
public:
    int divide(int dividend, int divisor) {
        //溢出
        if (dividend == INT_MIN && divisor == -1) return INT_MAX;
        if (divisor == 1) return dividend;
        bool flag = true;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) flag = false;
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;
        int res = 0;

        // 倍乘法，注意都是负数了，比较的时候与正数相反
        // 简单点理解，就是每次减去除数的 2^x 倍数，剩下的部分继续按这样的规则继续
        while (dividend <= divisor) {
            int tmp = divisor, cnt = 1;
            while (tmp >= dividend - tmp) {
                tmp += tmp;
                cnt += cnt;
            }
            dividend -= tmp;
            res += cnt;
        }
        return flag ? res : -res;
    }
};

int main() {
    Divide di;
    int res = di.divide(-2147483648,2);
    cout << res << endl;
}

